package search;

import java.util.Stack;

/**
 * 二叉排序树
 *
 * @author miweidong
 * @date 2021-09-03 10:16
 * https://www.cnblogs.com/wkfvawl/p/9901462.html
 */
public class BinarySearchTree {

    private static Node node;

    public static void main(String[] args) {
        int[] arr = {1, 2, 9, 8, 0, 4, 1};
        createBST(arr);
        System.out.println(node);
        System.out.println("--------先序遍历-------");
        preOrder(node);
        System.out.println("--------先序遍历递归-------");
        preOrderRec(node);
        System.out.println("------中序遍历--------");
        inOrder(node);
        System.out.println("--------中序遍历1-------");
        inOrder1(node);
        System.out.println("--------中序遍历递归-------");
        inOrderRec(node);
        System.out.println("------后序遍历---------");
        postOrder(node);
        System.out.println("------后序遍历递归---------");
        postOrderRec(node);

        System.out.println("---------计算一棵二叉树的所有结点-------");
        int bTreeNodes = getBTreeNodes(node);
        System.out.println("*********结点个数为:  " + bTreeNodes);


        System.out.println("---------输出一颗二叉树的所有叶子结点---------");
        dispLeaf(node);

        System.out.println("---------计算值为x的结点在树中的层次---------");
        int level = level(node, 12, 1);
        if (level == 0) {
            System.out.println("********未找到值匹配的结点***********");
        } else {
            System.out.println("********层次为： " + level);
        }

        System.out.println("---------输出一颗二叉树第k层的结点个数---------");
        lNodeNum(node, 1, 2);
        System.out.println("第k层结果：" + kNodes);

    }

    /**
     * 插入一个节点，如果值相同，插入失败
     *
     * @param key 插入值
     * @return 插入结果
     */
    public static boolean insertBST(int key) {
        if (null == node) {
            node = new Node();
            node.key = key;
            return true;
        }
        Node current = node;
        Node parentNode = null;
        while (current != null) {
            parentNode = current;
            if (current.key == key) {
                return false;
            }
            if (current.key > key) {
                current = current.lchild;
                if (current == null) {
                    parentNode.lchild = new Node();
                    parentNode.lchild.key = key;
                    return true;
                }
            } else {
                current = current.rchild;
                if (current == null) {
                    parentNode.rchild = new Node();
                    parentNode.rchild.key = key;
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 数组转换二叉排序树
     *
     * @param arr 数组
     */
    public static void createBST(int[] arr) {
        int i = 0;
        while (i < arr.length) {
            insertBST(arr[i]);
            i++;
        }
    }


    /**
     * 先序遍历
     *
     * @param node 二叉树
     */
    public static void preOrder(Node node) {
        Stack<Node> stack = new Stack<>();
        Node p = node;
        if (p != null) {
            stack.push(p);
            while (!stack.isEmpty()) {
                Node pop = stack.pop();
                System.out.println(pop.key);
                // 先进后出，右孩子先进栈，符合先序遍历思想
                if (pop.rchild != null) {
                    stack.push(pop.rchild);
                }
                if (pop.lchild != null) {
                    stack.push(pop.lchild);
                }
            }
        }
    }

    /**
     * 先序递归
     *
     * @param node 二叉树
     */
    public static void preOrderRec(Node node) {
        if (node != null) {
            System.out.println(node.key);
            preOrderRec(node.lchild);
            preOrderRec(node.rchild);
        }
    }


    /**
     * 中序遍历
     *
     * @param node 二叉树
     */
    public static void inOrder(Node node) {
        Stack<Node> stack = new Stack<>();
        Node p = node;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.lchild;
            }
            if (!stack.isEmpty()) {
                p = stack.pop();
                System.out.println(p.key);
                p = p.rchild;
            }
        }
    }

    /**
     * 中序遍历  （左、根、右）
     *
     * @param node 二叉树
     */
    public static void inOrder1(Node node) {
        Stack<Node> stack = new Stack<>();
        Node p = node;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.lchild;
            }
            if (!stack.isEmpty()) {
                p = stack.pop();
                System.out.println(p.key);
                p = p.rchild;
            }
        }
    }

    /**
     * 中序递归
     *
     * @param node 二叉树
     */
    public static void inOrderRec(Node node) {
        if (node != null) {
            inOrderRec(node.lchild);
            System.out.println(node.key);
            inOrderRec(node.rchild);
        }
    }

    /**
     * 后序遍历
     *
     * @param node 二叉树
     */
    public static void postOrder(Node node) {

    }


    /**
     * 后序递归
     *
     * @param node 二叉树
     */
    public static void postOrderRec(Node node) {
        if (node != null) {
            postOrderRec(node.lchild);
            postOrderRec(node.rchild);
            System.out.println(node.key);
        }
    }


    /**
     * 计算一颗给定二叉树的所有结点个数
     *
     * @param node 二叉树
     * @return 所有结点个数 包括根节点
     */
    public static int getBTreeNodes(Node node) {
        if (node == null) {
            return 0;
        }
        return getBTreeNodes(node.lchild) + getBTreeNodes(node.rchild) + 1;
    }


    /**
     * 输出一颗二叉树的所有叶子结点
     *
     * @param node 二叉树
     */
    public static void dispLeaf(Node node) {
        if (node != null) {
            if (node.lchild == null && node.rchild == null) {
                System.out.println(node.key);
            }
            dispLeaf(node.lchild);
            dispLeaf(node.rchild);
        }
    }

    /**
     * 计算值为x的结点在树中的层次
     *
     * @param node 二叉树
     * @param x    传入值
     * @param h    如果x存在的高度,初始化为1
     * @return x所在树的高度 返回0表示未找到
     */
    public static int level(Node node, int x, int h) {
        int l;
        if (node == null) {
            return 0;
        }
        if (node.key == x) {
            return h;
        }
        l = level(node.lchild, x, h + 1);
        if (l != 0) {
            return l;
        }
        return level(node.rchild, x, h + 1);
    }

    /**
     * 第k层结点个数全局变量
     */
    static int kNodes;

    /**
     * 输出一颗二叉树第k层的结点个数
     *
     * @param node 二叉树
     * @param h    高度
     * @param k    第k层
     */
    public static void lNodeNum(Node node, int h, int k) {
        if (node != null) {
            if (h == k) {
                kNodes++;
                // System.out.println(node.key);
            } else {
                lNodeNum(node.lchild, h + 1, k);
                lNodeNum(node.rchild, h + 1, k);
            }
        }
    }


}


class Node {
    int key;
    Node lchild;
    Node rchild;
}
